package problem109_Convert_Sorted_List_to_Binary_Search_Tree;

import problem108_Convert_Sorted_Array_to_Binary_Search_Tree.TreeNode;
import problem82_Remove_Duplicates_from_Sorted_List2.ListNode;

public class Solution {
	public TreeNode sortedListToBST(ListNode head) {
		if(head==null)
			return null;
		else if(head.next==null)
			return new TreeNode(head.val);
		ListNode p=head,q=head.next.next;
		while(q!=null&&q.next!=null){
			p=p.next;
			q=q.next.next;
		}
		TreeNode root=new TreeNode(p.next.val);
		root.right=sortedListToBST(p.next.next);
		p.next=null;
		root.left=sortedListToBST(head);
		return root;
    }
}
